package ClassicDataStructuresAndAlgorithms.ClassicLinkedListAlgorithms;

import java.util.Stack;

/**
 * 两数之和Ⅱ
 */

public class Solution445 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //首先申明两个栈，用来存放l1和l2的数据，真正实现l1和l2的反转
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        ListNode p1 = l1;
        ListNode p2 = l2;

        //依旧设置一个虚拟头节点
        ListNode dummy = new ListNode(-1);

        //carry用来表示进位
        int carry = 0;

        //将l1中的元素全部压入栈中
        while(p1!=null){
            stack1.push(p1.val);
            p1 = p1.next;
        }

        while(p2!=null){
            stack2.push(p2.val);
            p2 = p2.next;
        }

        //stack1和stack2仍有数字，或者还有进位，那么就得继续计算
        while(!stack1.isEmpty()||!stack2.isEmpty()||carry==1){
            int val = carry;
            //stack1非空，就得取出当前stack1中的一位进行计算
            if (!stack1.isEmpty()){
                int val1 = stack1.pop();
                val += val1;
            }
            //同理，stack2非空，取出stack2当前这一位，计算
            if (!stack2.isEmpty()){
                int val2 = stack2.pop();
                val +=val2;
            }

            //计算当前这一位的计算是否有进位
            carry = val / 10;
            //当前这一位真正要存的数字
            int num = val % 10;

            //用头插法把新节点插入到结果链表的开头
            //因为newNode表示的是高位的数字，得往前面插。
            ListNode newNode = new ListNode(num);
            newNode.next = dummy.next;
            dummy.next = newNode;
        }

        return dummy.next;
    }
}
